package leetcode_1000;

/**
 * @author 周杨
 * 2019年6月16日 下午3:52:17
 * ShortestCommonSupersequence_1092_.java
 * description: 给两个字符串 找出最短的一个字符串 使这两个字符串都是它的子序列 用动态规划 
 */
public class ShortestCommonSupersequence_1092_ {
	 public String shortestCommonSupersequence(String str1, String str2) {
	      int x = str1.length(),y = str2.length();
	      int dp[][] = new int[x+1][y+1];
	      for(int i=0;i<=x;++i) {
	    	  for(int j=0;j<=y;++j) {
	    		  if (i == 0)  {
	                    dp[i][j] = j; 
	                }  
	                else if (j == 0)   { 
	                    dp[i][j] = i; 
	                }  
	                else if (str1.charAt(i - 1) == str2.charAt(j - 1))  { 
	                    dp[i][j] = 1 + dp[i - 1][j - 1]; 
	                } 
	                else  { 
	                    dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]); 
	                } 
	    	  }
	      }
	        int now = dp[x][y]; 
	        String str = ""; 
	        int i = x, j = y; 
	        while (i > 0 && j > 0) { 
	            if (str1.charAt(i - 1) == str2.charAt(j - 1))    { 
	                // Put current character in result 
	            	str += (str1.charAt(i - 1)); 
	                i--; 
	                j--; 
	                now--; 
	            }  
	            else if (dp[i - 1][j] > dp[i][j - 1]) {  
	                str += (str2.charAt(j - 1)); 
	                j--; 
	                now--; 
	            }  
	            else {   
	                str += (str1.charAt(i - 1)); 
	                i--; 
	                now--; 
	            } 
	        }
	        while (i > 0)  
	        { 
	            str += (str1.charAt(i - 1)); 
	            i--; 
	            now--; 
	        } 
	        while (j > 0) 
	        { 
	            str += (str2.charAt(j - 1)); 
	            j--; 
	            now--; 
	        } 
	        str = reverse(str); 
	        return str; 
	 }
	 
	
	  
	    private String reverse(String input)  
	    { 
	        char[] temparray = input.toCharArray(); 
	        int left, right = 0; 
	        right = temparray.length - 1; 
	  
	        for (left = 0; left < right; left++, right--) 
	        { 
	            // Swap values of left and right  
	            char temp = temparray[left]; 
	            temparray[left] = temparray[right]; 
	            temparray[right] = temp; 
	        } 
	        return String.valueOf(temparray); 
	    } 
	 
	
}
